#include "RedBlackTree.h"
#include <stdio.h>
#include <assert.h>
#include <iostream>
#include <time.h>

RedBlackTree::RedBlackTree(void) : mRoot(NULL), nil(createNode(NULL))
{
	nil->color = BLACK;
}

RedBlackTree::~RedBlackTree(void)
{
	pTreeNode temp = mRoot;
	while (temp)
	{
		if (is_not_leaf(temp->left))
			temp = temp->left;
		else if (is_not_leaf(temp->right))
			temp = temp->right;
		else
		{
			mRoot = temp->parent;
			if (mRoot)
			{
				(mRoot->left == temp ? mRoot->left : mRoot->right) = NULL;
			}
			delete temp;
			temp = mRoot;
		}
	}
	delete nil;
}

pTreeNode RedBlackTree::createNode(pNodeData data)
{
	pTreeNode node = new TreeNode();
	node->parent = NULL;
	node->left = nil;
	node->right = nil;
	node->color = RED;
	node->m_pData = data;
	return node;
}

bool RedBlackTree::is_not_leaf(pTreeNode node) {
	return node != nil;
}

pTreeNode RedBlackTree::grandparent(pTreeNode node)
{
	return node->parent->parent;
}

pTreeNode RedBlackTree::uncle(pTreeNode node)
{
	return node->parent == grandparent(node)->left ? grandparent(node)->right : grandparent(node)->left;
}

pTreeNode RedBlackTree::sibling(pTreeNode node) {
	if (node->parent)
		return (node->parent->left == node ? node->parent->right : node->parent->left);
	else
		return NULL;
}

void RedBlackTree::left_rotate(pTreeNode pivot)
{
	pTreeNode root = pivot->parent;
	assert(root && root->right == pivot);

	pivot->parent = root->parent;
	if (root->parent)
	{
		if (root->parent->left == root)
		{
			root->parent->left = pivot;	
		}
		else
		{
			root->parent->right = pivot;
		}
	}
	else
	{
		mRoot = pivot;
	}

	root->parent = pivot;
	root->right = pivot->left;
	if (is_not_leaf(pivot->left))
		pivot->left->parent = root;
	pivot->left = root;

	int color = root->color;
	root->color = pivot->color;
	pivot->color = color;
}

void RedBlackTree::right_rotate(pTreeNode pivot)
{
	pTreeNode root = pivot->parent;
	assert(root && root->left == pivot);

	pivot->parent = root->parent;
	if (root->parent)
	{
		if (root->parent->left == root)
		{
			root->parent->left = pivot;	
		}
		else
		{
			root->parent->right = pivot;
		}
	}
	else
	{
		mRoot = pivot;
	}

	root->parent = pivot;
	root->left = pivot->right;
	if (is_not_leaf(pivot->right))
		pivot->right->parent = root;
	pivot->right = root;

	int color = root->color;
	root->color = pivot->color;
	pivot->color = color;
}

bool RedBlackTree::_insert(pTreeNode root, pTreeNode pNode)
{
	if (!root)
	{
		mRoot = pNode;
		return true;
	}

	int r = root->m_pData->compare(pNode->m_pData);
	if (r == 1)
	{
		if (is_not_leaf(root->left))
			return _insert(root->left, pNode);
		else
		{
			root->left = pNode;
			pNode->parent = root;
		}
	}
	else if (r == -1)
	{
		if (is_not_leaf(root->right))
			return _insert(root->right, pNode);
		else
		{
			root->right = pNode;
			pNode->parent = root;
		}
	}
	else
	{
		return false;
	}
	return true;
}

void RedBlackTree::insert_adjust(pTreeNode node)
{
	int state = 0;
	while (state != -1)
	{
		switch (state)
		{
		case 0:
			if (!node->parent) {
				node->color = BLACK;
				mRoot = node;
				state = -1;
				break;
			}
		case 1:
			if (node->parent->color == BLACK) {
				state = -1;
				break;
			}
		case 2:
			if (uncle(node)->color == RED)
			{
				node->parent->color = BLACK;
				uncle(node)->color = BLACK;
				grandparent(node)->color = RED;
				node = grandparent(node);
				state = 0;
				break;
			}
		case 3:
			if (grandparent(node)->left == node->parent)
			{
				if (node->parent->right == node) {
					left_rotate(node);
					node = node->left;
				}
				state = 4;
			}
			else /*if (grandparent(node)->right == node->parent)*/
			{
				if (node->parent->left == node) {
					right_rotate(node);
					node = node->right;
				}
				state = 5;
			}
			break;
		case 4:
			node = node->parent;
			right_rotate(node);
			state = -1;
			break;
		case 5:
			node = node->parent;
			left_rotate(node);
			state = -1;
			break;
		default:
			state = -1;
			break;
		}
	}
}

void RedBlackTree::insert(pNodeData data)
{
	if (!data)
		return;
	pTreeNode node = createNode(data);
	if (_insert(mRoot, node))
		insert_adjust(node);
	else
		delete node;
}

void RedBlackTree::_delete(pTreeNode node) {
	assert(!is_not_leaf(node->left) || !is_not_leaf(node->right));
	
	int state = 0;
	pTreeNode temp = node;
	pTreeNode sibling_node;
	pTreeNode child = is_not_leaf(node->left) ? node->left : node->right;
	child->parent = node->parent;
	if (node->parent) {
		(node->parent->left == node ? node->parent->left : node->parent->right) = child;
	}
	else if (is_not_leaf(child)) {
		mRoot = child;
	}
	else {
		mRoot = NULL;
		state = -1;
	}
	while (state != -1) {
		switch (state) {
		case 0:
			if (node->color == RED) {
				state = -1;
				break;
			}
			
			if (child->color == RED) {
				child->color = BLACK;
				state = -1;
				break;
			}
			node = child;
		case 1:
			if (!node->parent) {
				state = -1;
				break;
			}

			if (node == node->parent->left)
				state = 20;
			else
				state = 30;
		case 20:		// node is left child of his parent
		case 30:		// node is right child
			sibling_node = sibling(node);
			if (sibling_node->color == RED) {
				state == 20 ? left_rotate(sibling_node) : right_rotate(sibling_node);
			}
			else if (node->parent->color == BLACK && sibling_node->left->color == BLACK 
				&&  sibling_node->right->color == BLACK) {
				sibling_node->color = RED;
				node = node->parent;
				state = 1;
				break;
			}
			++state;
		case 21:
		case 31:
			sibling_node = sibling(node);
			if (node->parent->color == RED && sibling_node->color == BLACK && 
				sibling_node->left->color == BLACK && sibling_node->right->color == BLACK) {
				node->parent->color = BLACK;
				sibling_node->color = RED;
				state = -1;
			}
			else
				++state;
			break;
		case 22:
			sibling_node = sibling(node);
			if (sibling_node->color == BLACK && sibling_node->left->color == RED && sibling_node->right->color == BLACK) {
				right_rotate(sibling_node->left);
			}
		case 23:
			sibling_node = sibling(node);
			if (sibling_node->color == BLACK && sibling_node->right->color == RED) {
				left_rotate(sibling_node);
				sibling_node->right->color = BLACK;
			}
			state = -1;
			break;
		case 32:
			sibling_node = sibling(node);
			if (sibling_node->color == BLACK && sibling_node->left->color == BLACK && sibling_node->right->color == RED) {
				left_rotate(sibling_node->right);
			}
		case 33:
			sibling_node = sibling(node);
			if (sibling_node->color == BLACK && sibling_node->left->color == RED) {
				right_rotate(sibling_node);
				sibling_node->left->color = BLACK;
			}
			state = -1;
			break;
		default:
			state = -1;
			break;
		}
	}
	delete temp;
}

void RedBlackTree::deleteData(pNodeData data)
{
	if (!data)
		return;

	pTreeNode node = search(data);
	if (!node)
		return;
	
	pTreeNode node2 = node;
	if (is_not_leaf(node->left)) {
		for (node2 = node->left; is_not_leaf(node2->right); node2 = node2->right);
	}
	else if (is_not_leaf(node->right)){
		for (node2 = node->right; is_not_leaf(node2->left); node2 = node2->left);
	}
	node->m_pData = node2->m_pData;
	_delete(node2);
}

pTreeNode RedBlackTree::search(pNodeData data)
{
	pTreeNode node = mRoot;
	while (node && is_not_leaf(node))
	{
		int r = node->m_pData->compare(data);
		if (r == -1)
		{
			node = node->right;
		}
		else if (r == 1)
		{
			node = node->left;
		}
		else if (r == 0)
		{
			break;
		}
		else
		{
			return NULL;
		}
	}
	return is_not_leaf(node) ? node : NULL;
}

bool RedBlackTree::check_tree() {
	int state = 0;
	int bh = 0;
	int max_bh = -1;
	pTreeNode node = mRoot;
	while (node) {
		switch (state) {
		case 0:
			if (node->color == BLACK) {
				++bh;
			}
			else if (!node->parent) {
				std::cout << "root is red, check failed." << std::endl;
				return false;
			}
			else if (node->parent->color == RED || node->left->color == RED || node->right->color == RED) {
				std::cout << "red parent has red child, check failed." << std::endl;
				return false;
			}
		case 1:
			if (is_not_leaf(node->left)) {
				node = node->left;
				state = 0;
				break;
			}
		case 2:
			if (is_not_leaf(node->right)) {
				node = node->right;
				state = 0;
				break;
			}
		case 3:
			if (max_bh == -1)
				max_bh = bh;
			else if (!(max_bh == bh || is_not_leaf(node->left) && is_not_leaf(node->right))) {
				std::cout << "break tree having the same black node depth, check failed." << std::endl;
				return false;		
			}

			if (node->color == BLACK)
				--bh;
			if (node->parent)
				state = node->parent->left == node ? 2 : 3;
			node = node->parent;
			break;
		}
	}
	return true;
}

int unit_test() {
	const int size = 20000;
	NodeData datas[size];
	for (int i = 0; i < size; ++i)
	{
		datas[i].mValue = i;
	}

	unsigned t = time(NULL);
	//t = 1331901565;
	srand(t);
	for (int i = 0; i < size; ++i)
	{
		int index = i + ((unsigned) rand()) % (size - i);
		NodeData temp = datas[index];
		datas[index] = datas[i];
		datas[i] = temp;
	}

	std::cout << "begin construct red-black tree." << std::endl;
	RedBlackTree tree;
	for (int i = 0; i < size; ++i)
	{
		tree.insert(datas + i);
		if (!tree.check_tree())
		{
			std::cout << "construct red-black tree failed" << std::endl;
			return 0;
		}
	}

	std::cout << "begin searching test." << std::endl;
	for (int i = 0; i < size; ++i)
	{
		if (!tree.search(datas + i))
		{
			std::cout << "search error 1 - " << i << std::endl;
		}
	}

	NodeData data0;
	data0.mValue = size;
	if (tree.search(&data0))
	{
		std::cout << "search error 2" << std::endl;
		return 0;
	}

	std::cout << "begin deleting test." << std::endl;
	for (int i = 0; i < size; ++i)
	{
		tree.deleteData(datas + i);
		if (!tree.check_tree())
		{
			std::cout << "red-black tree delete exception" << std::endl;
			return 0;
		}
	}
	std::cout << "test red-black tree successful!" << std::endl;
}

int main()
{
	int size = 100;
	for (int i = 0; i < size; ++i)
		unit_test();

	char c; 
	std::cin >> c;
}